package leecode.array;

import java.util.ArrayList;

/**
 * @author wangxi created on 2021/5/17 23:53
 * @version v1.0
 *
 * 给出一组区间，请合并所有重叠的区间。
 * 请保证合并后的区间按区间起点升序排列。
 *
 * from nowcoder
 */
public class MergeIntervalsV2 {

    public class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        if (intervals == null || intervals.size() <= 0) {
            return res;
        }
        intervals.sort((x, y) -> Integer.compare(x.start, y.start));
        // 提前先添加一个元素，这样的话写起来就顺畅多了
        res.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            Interval left = res.get(res.size() - 1);
            Interval right = intervals.get(i);
            if (left.end >= right.start && left.end <= right.end) {
                left.end = right.end;
            } else if (left.end < right.start) {
                res.add(right);
            }
        }
        return res;
    }
}
